棋盘问题——算法系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）


  回溯算法的本质：它是一种深度优先搜索（DFS）的暴力枚举策略，核心是“尝试 - 回退”—— 在解决问题的过程中，一步步尝试所有可能的选择，当发现当前选择无法得到合法解时，就回退到上一步，撤销当前选择，继续尝试其他可能，直到找到所有解 / 一个合法解。

棋盘问题

教程目录导航

▼

一、N 皇后问题（LeetCode 51/52）

问题描述：

算法解析：

N 皇后的核心是逐行放置皇后（天然避免同行冲突），再通过回溯法尝试每一行的每一列，同时提前校验列、正对角线、反对角线是否已有皇后（剪枝，避免无效递归），具体思路：

  1. 逐行放置：从第 0 行开始，依次为每一行选择一个合法列放置皇后，一行放完再放下一行，直到第 n 行（所有行放置完成，得到一个合法方案）；
  2. 冲突校验：放置前检查 3 个条件，任意一个不满足则跳过该列：
    • 列冲突：该列是否已有皇后；
    • 正对角线（左上→右下）冲突：行号 - 列号为固定值，需保证该值未被占用；
    • 反对角线（右上→左下）冲突：行号 + 列号为固定值，需保证该值未被占用；
  3. 回溯还原：若当前列放置后，后续行无合法位置，就撤销当前行的皇后放置，尝试当前行的下一列；
  4. 结果构造：合法方案生成后，将棋盘状态（皇后位置用 Q，空位置用 .）转换为题目要求的字符串数组格式。

关键技巧：冲突快速校验

直接遍历棋盘校验冲突的时间复杂度较高，用三个布尔数组记录占用状态，能实现 O(1) 时间校验：

  1. col[n]：col[j] = true 表示第 j 列已有皇后；
  2. diag1[2n-1]：记录正对角线占用，下标为 i - j + n - 1（偏移 n-1 避免负数）；
  3. diag2[2n-1]：记录反对角线占用，下标为 i + j。

#include <iostream>
#include <vector>
using namespace std;

vector<vector<string>> res_nQueens;  // 存储所有合法方案
vector<string> board;        // 模拟棋盘，每一行是一个字符串
vector<bool> col;            // 标记列是否被占用
vector<bool> diag1;          // 标记正对角线（i-j）是否被占用
vector<bool> diag2;          // 标记反对角线（i+j）是否被占用
int n;                       // 棋盘大小

// 回溯函数：处理第row行的皇后放置
void nQueens(int row) {
    // 终止条件：所有行都放置了皇后，找到合法方案
    if (row == n) {
        res_nQueens.push_back(board);
        return;
    }
    // 遍历当前行的所有列，尝试放置皇后
    for (int j = 0; j < n; ++j) {
        // 计算对角线索引，避免diag1下标为负
        int d1 = row - j + n - 1;
        int d2 = row + j;
        // 剪枝：列/正对角线/反对角线有皇后，跳过该列
        if (col[j] || diag1[d1] || diag2[d2]) {
            continue;
        }

        // 选择：在(row, j)放置皇后
        board[row][j] = 'Q';
        col[j] = true;
        diag1[d1] = true;
        diag2[d2] = true;

        // 递归：处理下一行
        nQueens(row + 1);

        // 回溯：撤销选择，还原状态
        board[row][j] = '*';
        col[j] = false;
        diag1[d1] = false;
        diag2[d2] = false;
    }
}

int main() {
    n = 4;

    // 初始化棋盘：n行，每行n个'*'
    board.assign(n, string(n, '*'));
    // 初始化标记数组，大小按需分配
    col.assign(n, false);
    diag1.assign(2 * n - 1, false);
    diag2.assign(2 * n - 1, false);
    // 从第0行开始回溯
    nQueens(0);

    for(vector<string> item : res_nQueens)
    {
        cout << "[";
        for(string node : item )
        {
            cout << " " << node << " ";
        }
        cout << "]" << endl;
    }

    return 0;
}

输出结果


[ *Q**  ***Q  Q***  **Q* ]
[ **Q*  Q***  ***Q  *Q** ]

二、数独求解（LeetCode 37）

问题描述：

算法解析：

解数独和 N 皇后的回溯逻辑一脉相承，但更复杂 —— 需要遍历棋盘所有空位置，为每个空位置尝试合法数字（1-9），同时通过快速校验剪枝，具体核心思路：

  1. 遍历空位置：按行优先顺序遍历棋盘的每个格子，遇到已填充数字（非.）直接跳过，遇到空位置则尝试填充；
  2. 合法数字校验：为当前空位置 (i,j) 尝试数字 1-9 时，需满足 3 个条件（缺一不可）：
    • 行合法：第 i 行无该数字；
    • 列合法：第 j 列无该数字；
    • 3×3 子数独合法：该格子所属的 3×3 小棋盘内无该数字；
  3. 回溯 + 剪枝：填充合法数字后，递归处理下一个空位置；若后续无合法填充方案，回溯（将当前位置还原为.），尝试下一个数字；
  4. 提前终止递归：数独有唯一解，因此找到合法解后直接返回 true，无需遍历所有可能（这是和 N 皇后、组合排列的核心区别）。

关键技巧：

  1. 3×3 子数独定位：对于位置 (i,j)，其所属 3×3 子数独的左上角坐标为 (i/3*3, j/3*3)（整数除法，向下取整）；
  2. 布尔返回值：回溯函数返回 bool，找到唯一解后立即终止所有递归，避免无效计算；
  3. 原地修改棋盘：直接在输入的棋盘上填充数字，无需额外存储，节省空间。

#include <iostream>
#include <vector>

using namespace std;

int matrix = 9; // 数独固定为9×9

// 校验函数：判断在(i,j)位置填充数字c是否合法
bool isValid(vector<vector<char>>& board, int i, int j, char c) {
    for (int k = 0; k < matrix; ++k) {
        // 检查第i行是否有c（列遍历）
        if (board[i][k] == c) return false;
        // 检查第j列是否有c（行遍历）
        if (board[k][j] == c) return false;
        // 检查所属3×3子数独是否有c
        // 核心：计算3×3子数独内的格子坐标 (i/3*3 + k/3, j/3*3 + k%3)
        int x = i / 3 * 3 + k / 3;
        int y = j / 3 * 3 + k % 3;
        if (board[x][y] == c) return false;
    }
    return true;
}

// 回溯函数：填充数独，找到解返回true，否则返回false
bool sudoku(vector<vector<char>>& board) {
    // 行优先遍历整个9×9棋盘
    for (int i = 0; i < matrix; ++i) {
        for (int j = 0; j < matrix; ++j) {
            if (board[i][j] != '.') continue; // 跳过已填充的格子

            // 尝试为当前空位置填充1-9的合法数字
            for (char c = '1'; c <= '9'; ++c) {
                if (isValid(board, i, j, c)) { // 校验数字c是否合法
                    // 选择：填充合法数字
                    board[i][j] = c;
                    // 递归：处理后续空位置，找到解则直接返回true（提前终止）
                    if (sudoku(board)) return true;
                    // 回溯：撤销选择，还原为空位置
                    board[i][j] = '.';
                }
            }
            // 1-9都尝试过，无合法数字，返回false表示当前路径无解
            return false;
        }
    }
    // 遍历完所有格子，无空位置，说明数独已解，返回true
    return true;
}

int main() {
    vector<vector<char>> board = {
        {'5','3','.','.','7','.','.','.','.'},
        {'6','.','.','1','9','5','.','.','.'},
        {'.','9','8','.','.','.','.','6','.'},
        {'8','.','.','.','6','.','.','.','3'},
        {'4','.','.','8','.','3','.','.','1'},
        {'7','.','.','.','2','.','.','.','6'},
        {'.','6','.','.','.','.','2','8','.'},
        {'.','.','.','4','1','9','.','.','5'},
        {'.','.','.','.','8','.','.','7','9'}
    };
    sudoku(board);

    for(vector<char> item : board)
    {
        cout << "[";
        for(char node : item )
        {
            cout << " " << node << " ";
        }
        cout << "]" << endl;
    }

    return 0;
}

输出结果


[ 5  3  4  6  7  8  9  1  2 ]
[ 6  7  2  1  9  5  3  4  8 ]
[ 1  9  8  3  4  2  5  6  7 ]
[ 8  5  9  7  6  1  4  2  3 ]
[ 4  2  6  8  5  3  7  9  1 ]
[ 7  1  3  9  2  4  8  5  6 ]
[ 9  6  1  5  3  7  2  8  4 ]
[ 2  8  7  4  1  9  6  3  5 ]
[ 3  4  5  2  8  6  1  7  9 ]

返回顶部